#include <iostream>
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
        //初始化数组
        std::vector<int> answer;
        answer.resize(temperatures.size(), 0);

        //单调栈，存放的是元素对应的下标
        std::stack<int> st;

        for(int i = 0; i < temperatures.size(); i++)
        {
            if(i == 0)
            {
                st.push(i);
                continue;
            }
            //如果元素比栈的大，则出栈，并更新answer的值
            while(st.size() != 0 && temperatures[i] > temperatures[st.top()])
            {
                answer[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
        return answer;
    }
};

//单调栈的应用，配合数组下标，